package Tree;

import java.util.LinkedList;
import java.util.Stack;

public class Tree2 {
    //二叉树的非递归遍历
    //二叉树节点
    public static class TreeNode{
        int data ; //节点
        TreeNode leftChild ; //左孩子
        TreeNode rightChild ; //右孩子

        TreeNode(int data){
            this.data = data ;
        }
    }


    //构建二叉树
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList){
        TreeNode node = null;
        if (inputList == null ||inputList.isEmpty()){
            return null;
        }
        Integer data = inputList.removeFirst() ;
        if(data != null){
            node = new TreeNode(data) ;
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList) ;
        }
        return node;
    }


    //前序非递归遍历  根左右
    public static void NonRecursivePreamble (TreeNode node){
        Stack<TreeNode> stack = new Stack<TreeNode>() ;
        TreeNode treeNode = node ;
        while (treeNode != null || !stack.isEmpty()){
            while (treeNode != null){
                System.out.println(treeNode.data);
                stack.push(treeNode);
                treeNode = treeNode.leftChild ;
            }
            if (!stack.isEmpty()){
                treeNode = stack.pop() ;
                treeNode = treeNode.rightChild ;
            }
        }
    }

    //中序非递归遍历  左根右
    public static void NonRecursiveMiddleOrder (TreeNode node){
        Stack<TreeNode> stack = new Stack<TreeNode>() ;
        TreeNode treeNode = node ;
        while (treeNode != null || !stack.isEmpty()){
            if (node != null) {
                stack.push(node);
                node = node.leftChild;
            } else {
                node = stack.pop();
                System.out.print(node.data + " ");
                node = node.rightChild;
            }
        }
    }

    //后序非递归遍历  左右根
    public static void NonRecursivePostorder (TreeNode node){
        if (node != null) {
            Stack<TreeNode> s1 = new Stack<TreeNode>();
            Stack<TreeNode> s2 = new Stack<TreeNode>();
            s1.push(node);
            while (!s1.isEmpty()) {
                node = s1.pop();
                s2.push(node);
                if (node.leftChild != null) {
                    s1.push(node.leftChild);
                }
                if (node.rightChild != null) {
                    s1.push(node.rightChild);
                }
            }
            while (!s2.isEmpty()) {
                System.out.print(s2.pop().data + " ");
            }
        }
        System.out.println();
    }
}
